//给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。 
//
// “最近的”定义为两个整数差的绝对值最小。 
//
// 
//
// 示例 1: 
//
// 
//输入: n = "123"
//输出: "121"
// 
//
// 示例 2: 
//
// 
//输入: n = "1"
//输出: "0"
//解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= n.length <= 18 
// n 只由数字组成 
// n 不含前导 0 
// n 代表在 [1, 10¹⁸ - 1] 范围内的整数 
// 
// Related Topics 数学 字符串 👍 129 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class _564_FindTheClosestPalindrome {
    public static void main(String[] args) {
        Solution solution = new _564_FindTheClosestPalindrome().new Solution();
        String s = "1283";
        System.out.println(solution.nearestPalindromic(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public String nearestPalindromic(String s) {
            List<Long> candidates = new ArrayList<>();
            candidates = processS(s);
            long num = Long.parseLong(s);
            long res = num;
            long min = Long.MAX_VALUE;
            for (long n : candidates) {
                if (n != num) {
                    long abs = Math.abs(num - n);
                    res = abs <= min ? (abs == min ? Math.min(n, res) : n) : res;
                    min = abs < min ? abs : min;
                }
            }

            return String.valueOf(res);
        }

        private List<Long> processS(String s) {
            int len = s.length();
            List<Long> res = new ArrayList<>();
            res.add((long)Math.pow(10, len - 1) - 1);
            res.add((long)Math.pow(10, len) + 1);

            long num = Long.parseLong(s);
            int[] nums = numToNums(num);
            for (int i = 0; i < len / 2; i++) {
                nums[len - i - 1] = nums[i];
            }
            res.add(numsToNum(nums));
            if (len % 2 == 0) {
                int n = nums[len / 2];
                int index = len / 2;

                if (n != 0) {
                    nums[index] = n - 1;
                    nums[index - 1] = n - 1;
                    res.add(numsToNum(nums));
                }
                if (n != 9) {
                    nums[index] = n + 1;
                    nums[index - 1] = n + 1;
                    res.add(numsToNum(nums));
                }
            } else {
                int n = nums[len / 2];
                int index = len / 2;

                if (n != 0) {
                    nums[index] = n - 1;
                    res.add(numsToNum(nums));
                } else if (n != 9) {
                    nums[index] = n + 1;
                    res.add(numsToNum(nums));
                }
            }

            return res;
        }

        private long numsToNum(int[] nums) {
            long res = 0;
            for (int n : nums) {
                res = res * 10;
                res += n;
            }
            return res;
        }

        private int[] numToNums(long num) {
            int len = String.valueOf(num).length();
            int[] nums = new int[len];

            for (int i = len - 1; i >= 0; i--) {
                nums[i] = (int) num % 10;
                num = num / 10;
            }
            return nums;
        }
    }

    class Solution2 {
        public String nearestPalindromic(String n) {
            long selfNumber = Long.parseLong(n), ans = -1;
            List<Long> candidates = getCandidates(n);
            for (long candidate : candidates) {
                if (candidate != selfNumber) {
                    if (ans == -1 ||
                            Math.abs(candidate - selfNumber) < Math.abs(ans - selfNumber) ||
                            Math.abs(candidate - selfNumber) == Math.abs(ans - selfNumber) && candidate < ans) {
                        ans = candidate;
                    }
                }
            }
            return Long.toString(ans);
        }

        public List<Long> getCandidates(String n) {
            int len = n.length();
            List<Long> candidates = new ArrayList<Long>() {{
                add((long) Math.pow(10, len - 1) - 1);
                add((long) Math.pow(10, len) + 1);
            }};
            long selfPrefix = Long.parseLong(n.substring(0, (len + 1) / 2));
            for (long i = selfPrefix - 1; i <= selfPrefix + 1; i++) {
                StringBuffer sb = new StringBuffer();
                String prefix = String.valueOf(i);
                sb.append(prefix);
                StringBuffer suffix = new StringBuffer(prefix).reverse();
                sb.append(suffix.substring(len & 1));
                String candidate = sb.toString();
                candidates.add(Long.parseLong(candidate));
            }
            return candidates;
        }
    }


    class Solution1 {
        public String nearestPalindromic(String n) {
            int len = n.length();
            long num = Long.parseLong(n);


//            int i = 1;
            long i = 1;
            while (!isPalindromic(numToNums(num - i)) && !isPalindromic(numToNums(num + i))) {
                i++;
            }
            return isPalindromic(numToNums(num - i)) ? String.valueOf(num - i) : String.valueOf(num + i);
//            System.out.println(Arrays.toString(nums));
//            System.out.println(isPalindromic(nums));
        }

        private long[] numToNums(long num) {
            int len = String.valueOf(num).length();
            long[] nums = new long[len];

            for (int i = len - 1; i >= 0; i--) {
                nums[i] = num % 10;
                num = num / 10;
            }
            return nums;
        }

        private boolean isPalindromic(long[] nums) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != nums[nums.length - i - 1]) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}